package com.algrithom.sort.insertsort;

import java.util.Arrays;

import com.util.CommonUtil;

/**
 * 希尔排序
 *
 * @author think
 * @version 1.0.0
 * @since 2020/1/1
 */
class XierSort {
    
    private static final int VALUE_THREE = 3;
    
    private static final XierSort xierSort = null;
    
    public static void main(String[] args){
        int[] array = {1,3,4,2,1,10,5};
        shellSort2(array);
        System.out.println(Arrays.toString(array));
    }
    
    /**
     * 希尔排序
     *
     * <p>
     * 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1） 2. 按增量序列个数k，对序列进行k 趟排序； 3.
     * 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     *
     * @param arr 待排序数组
     */
    public static void shellSort1(int[] arr){
        int gap = arr.length / 2;
        // 不断缩小gap，直到1为止
        for (; gap > 0; gap /= 2) {
            // 使用当前gap进行组内插入排序
            for (int j = 0; (j + gap) < arr.length; j++) {
                for (int k = 0; (k + gap) < arr.length; k += gap) {
                    if (arr[k] > arr[k + gap]) {
                        // 交换操作
                        int temp = arr[k + gap];
                        arr[k + gap] = arr[k];
                        arr[k] = temp;
                        System.out.println("Sorting: " + Arrays.toString(arr));
                    }
                }
            }
        }
    }
    
    /**
     * 希尔排序（Wiki官方版）
     *
     * <p>
     * 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（注意此算法的gap取值） 2. 按增量序列个数k，对序列进行k 趟排序； 3.
     * 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。 仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     *
     * @param arr 待排序数组
     */
    public static void shellSort2(int[] arr){
        int gap = 1, i, j, len = arr.length;
        int temp;
        while (gap < len / 3) {
            gap = gap * 3 + 1;
        }
        for (; gap > 0; gap /= 3) {
            for (i = gap; i < len; i++) {
                temp = arr[i];
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }
        }
    }
    
    /**
     * 希尔排序
     *
     * @param array 数组
     */
    void shellSort(Integer[] array){
        int len = array.length;
        int counter = 1;

        int h = 1;
        // 确定第一轮排序时的间隔
        while (VALUE_THREE * h + 1 < len) {
            h = 3 * h + 1;
        }

        while (h > 0) {
            for (int i = 0; i < h; i++) {
                // 对间隔为h的元素进行插入排序
                shellInsertSort(array,i,h);
            }

            // 下一轮排序的间隔
            h = (h - 1) / 3;

            System.out.print("第" + counter + "轮排序结果：");
            CommonUtil.display(array);
            counter++;
        }
    }
    
    /**
     * 希尔排序内部使用的插入排序:
     * 需要进行插入排序的元素为array[beginIndex]、array[beginIndex+increment]、array[beginIndex+2*increment]...
     *
     * @param beginIndex 起始下标
     * @param increment 增量
     */
    private void shellInsertSort(Integer[] array,int beginIndex,int increment){
        // 欲插入元素的下标
        int targetIndex = beginIndex + increment;

        while (targetIndex < array.length) {
            int temp = array[targetIndex];
            // 前一个元素下标，间隔为increment
            int previousIndex = targetIndex - increment;
            while (previousIndex >= 0 && array[previousIndex] > temp) {
                // 比欲插入数据项大的元素后移一位
                array[previousIndex + increment] = array[previousIndex];
                previousIndex = previousIndex - increment;
            }
            // 插入到合适的位置
            array[previousIndex + increment] = temp;
            // 插入下一个元素
            targetIndex = targetIndex + increment;
        }
    }
}
